home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / COMAL / Z-Misc Series / (k)zk.d64 / txt.grammar < prev    next >
Text File  |  2007-03-01  |  6KB  |  294 lines
  1. ╙╧═┼ ╠╔╬╟╒╔╙╘╔├╙ ┴╬─ ╨╧┼╘╥┘
  2.  
  3. BY ─ICK ╦LINGENS
  4. ─UTCH ├╧═┴╠ ╒SERS ╟ROUP
  5.  
  6. ┴ PROGRAMMING LANGUAGE CAN BE
  7. DESCRIBED WITH SO CALLED PRODUCTION
  8. RULES: RULES THAT PRODUCE PROGRAMS
  9. WRITTEN IN THAT PROGRAMMING LANGUAGE.
  10. ╙UCH RULES FOR ├╧═┴╠ CAN BE FOUND IN
  11. ╠EN ╠INDSAY'S ├╧═┴╠ ╚ANDBOOK (PAGES
  12. 413-422).
  13.  
  14. ┴ CONTEXT FREE GRAMMAR IS A FORMAL
  15. DESCRIPTION OF THE GRAMMAR OF A
  16. LANGUAGE. ╬OTIONS OF THE LANGUAGE ARE
  17. DESCRIBED (OR DEFINED) IN TERMS OF
  18. OTHER NOTIONS OR FINALLY IN TERMS OF
  19. WORDS FROM THE LANGUAGE. ╘HE
  20. PRODUCTION RULES FOR ├╧═┴╠ FORM AN
  21. (ALMOST) CONTEXT FREE GRAMMAR FOR
  22. ├╧═┴╠.
  23.  
  24. ┴N EXAMPLE.
  25.  
  26. <IDENTIFIER> MEANS: THE NOTION
  27. 'IDENTIFIER' OR, IN OTHER WORDS,
  28. 'WHAT IS AN IDENTIFIER'.
  29.  
  30. ::= MEANS: IS DEFINED BY.
  31.  
  32. ╔N THE ├╧═┴╠ KERNAL (LAST LINE ON
  33. PAGE 417) WE FIND IN A MODIFIED WAY:
  34.  
  35. 1. <INTEGER>::=
  36.       <DIGIT>!<DIGIT><INTEGER> 
  37.  
  38. 2. <DIGIT>::=0!1!2!3!4!5!6!7!8!9
  39.  
  40. IN WHICH ! MEANS ╧╥.
  41.  
  42. ╘HE NOTIONS NOT WRITTEN BETWEEN < AND
  43. > ARE CALLED TERMINAL SYMBOLS.
  44.  
  45. ╘O FIND OUT WHETHER 1234 IS AN
  46. <INTEGER> OR NOT WE HAVE:
  47.  
  48. 1234 = 1 234 
  49.  
  50. ╞OLLOWING THE SECOND PART OF RULE 1: 
  51. 1 IS A DIGIT AND WE NOW EXAMINE 234.
  52. ╔S IT AN INTEGER?
  53.  
  54. 234 = 2 34
  55.  
  56. 2 IS A DIGIT AND WE NOW EXAMINE 34.
  57. ╔S IT AN INTEGER?
  58.  
  59. 34 = 3 4 
  60.  
  61. 3 IS A DIGIT AND WE NOW EXAMINE 4. ╔S
  62. IT AN INTEGER? ┘ES, THAT FOLLOWS FROM
  63. FIRST PART OF RULE 1.
  64.  
  65. ╙O 1234 IS AN INTEGER.
  66.  
  67. ╘HE ├╧═┴╠ KERNAL DESCRIBES IN A
  68. FORMAL WAY WHAT A PROGRAM IS.
  69. ╘HEREFOR THE FIRST PRODUCTION RULE OF
  70. THE KERNAL IS
  71.  
  72. <COMAL PROGRAM>::=<BLOCK>
  73.  
  74. ╨ARTS OF A NATURAL LANGUAGE SOMETIMES
  75. CAN BE DESCRIBED IN THE SAME WAY.
  76. ╘HERE IS HOWEVER A SLIGHT (BIG)
  77. DIFFERENCE: SENTENCES ARE SOMETIMES
  78. MEANINGLESS BUT SYNTACTICALLY CORRECT
  79. ACCORDING TO THE RULES.
  80.  
  81. ╔N THE PROGRAM '┴ ├╞ ╟╥┴══┴╥' ╔
  82. DESCRIBE A CONTEXT FREE GRAMMAR FOR
  83. SOME ┼NGLISH SENTENCES, INSPIRED BY
  84. THE ┴MERICAN SONG '═ARY HAD A LITTLE
  85. LAMB'.
  86.  
  87. ╘O PRODUCE UNEXPECTED SENTENCES ╔
  88. USED ON SEVERAL PLACES IN THE SYNTAX
  89. A CONTRUCTION LIKE
  90.  
  91. <ARTICLE>::=[0.45] A ! THE
  92.  
  93. WHICH MEANS
  94.  
  95. THE PROBABILITY FOR CHOOSING "A" AS
  96. AN <ARTICLE> IS 0.45; THE ALTERNATIVE
  97. "THE" HAS PROBABILITY 1 - 0.45 = 0.55
  98. "A" AND "THE" ARE TERMINAL SYMBOLS.
  99.  
  100. ╘HE PRODUCTION OF A SENTENCE STARTS
  101. WITH
  102. <SENTENCE>::=<SUBJECT><PREDICATE>
  103. <ENDSYMBOL>
  104.  
  105. <SUBJECT>::=[0.7]<SUBSTANTIVE GROUP>!
  106.             <PERSONAL PRONOUN 1>
  107. <SUBSTANTIVE GROUP>::=<ARTICLE><NOUN
  108. PHRASE>
  109.  
  110. ╔T IS EASY TRANSFORM THE GRAMMAR INTO
  111. A ├╧═┴╠ PROGRAM THAT PRODUCES THE
  112. SENTENCES:
  113.  
  114. ╨╥╧├ SENTENCE
  115.   SUBJECT; PREDICATE; ENDSYMBOL
  116. ┼╬─╨╥╧├ SENTENCE
  117. //
  118. ╨╥╧├ SUBJECT
  119.   ╔╞ P(0.7) ╘╚┼╬
  120.     SUBSTANTIVE'GROUP
  121.   ┼╠╙┼
  122.     PERSONAL'PRONOUN'1
  123.   ┼╬─╔╞
  124. ┼╬─╨╥╧├ SUBJECT
  125. //
  126. ╨╥╧├ SUBSTANTIVE'GROUP
  127.   ARTICLE; NOUN'PHRASE
  128. ┼╬─╨╥╧├ SUBSTANTIVE'GROUP
  129. //
  130. ╨╥╧├ ARTICLE
  131.   ╔╞ P(0.45) ╘╚┼╬  
  132.     SYMBOL("A")
  133.   ┼╠╙┼ 
  134.     SYMBOL("THE")
  135.   ┼╬─╔╞
  136. ┼╬─╨╥╧├ ARTICLE
  137. //
  138. ╨╥╧├ ENDSYMBOL
  139.   ╨╥╔╬╘
  140. ┼╬─╨╥╧├ ENDSYMBOL
  141. //
  142. ╞╒╬├ P(X) ├╠╧╙┼─
  143.   ╥┼╘╒╥╬ ╥╬─<X
  144. ┼╬─╞╒╬├ P
  145. //
  146. // ╘HE OTHER RULES CAN BE FOUND IN
  147. // THE PROGRAM LISTING
  148.  
  149. ╘O PRINT THE TERMINAL SYMBOLS ON THE
  150. SCREEN WE USE
  151.  
  152. ╨╥╧├ SYMBOL(X$)
  153.  ╨╥╔╬╘ X$+" ",
  154. ┼╬─╨╥╧├ SYMBOL
  155.  
  156. ╘HE GRAMMAR IS CALLED A PROBABLISTIC
  157. CONTEXT FREE LANGUAGE BECAUSE
  158. PROBABILITIES ARE USED DURING
  159. PRODUCTION. ╙OME PRODUCED SENTENCES
  160. ARE
  161.  
  162. - THE BEAR THAT SEES THE BEAR LIKES A
  163.   BAD BEAR
  164. - THE BEAR LIKES HIM
  165. - THE BOY DREAMS ABOUT THE BEAR
  166. - A GIRL NEVER SEES THE GIRL
  167. - ╩IM SEES ═ARY
  168. - A BOY THAT SEES THE BIG TREE ALWAYS
  169.   LIKES A BOY THAT ALWAYS EATS A TREE
  170. - ═ARY EATS A LITTLE BEAR
  171.  
  172. ╔N CONTEXT FREE GRAMMARS RECURSION IS
  173. OFTEN USED TO DEFINE NOTIONS:
  174.  
  175. <NOUN PHRASE>::=
  176.    [0.25]<ADJECTIVE><NOUN PHRASE>!
  177.  
  178. <NOUNPART>
  179.  
  180. ┴ND BECAUSE ├╧═┴╠ ITSELF ALLOWS
  181. RECURSION TRANSFORMING THIS RULE CAN
  182. BE ACCOMPLISHED IN A VERY NATURAL WAY
  183.  
  184. ╨╥╧├ NOUN'PHRASE
  185.   ╔╞ P(0.25) ╘╚┼╬
  186.     ADJECTIVE
  187.     NOUN'PHRASE // ├╧═┴╠ RECURSION!
  188.   ┼╠╙┼
  189.     NOUNPART
  190.   ┼╬─╔╞
  191. ┼╬─╨╥╧├ NOUN'PHRASE
  192.  
  193. ╫HAT ABOUT WRITING A ├╧═┴╠ PROGRAM
  194. NOW THAT PRODUCES ├╧═┴╠ PROGRAMS?
  195.  
  196. ╞IRST THE PRODUCTION RULES FOR A VERY
  197. ╘╔╬┘├╧═┴╠:
  198.  
  199. <PROGRAM>       ::=<STATEMENT LIST>
  200. <STATEMENT LIST>::=<STATEMENT>!
  201. <STATEMENT LIST>
  202. <STATEMENT>     ::=<IDENTIFIER>:=
  203. <BOOLEAN><NEW LINE>
  204. <IDENTIFIER>    ::=A
  205. <BOOLEAN>       ::=╘╥╒┼ ! ╞┴╠╙┼
  206. <NEW LINE>      ::=
  207.  
  208. ╘HE LAST NOTION <NEW LINE> MEANS THAT
  209. EVERY STATEMENT STARTS ON A NEW LINE.
  210.  
  211. ╘HE ├╧═┴╠ PROGRAM:
  212.  
  213. PROGRAM
  214. //
  215. ╨╥╧├ PROGRAM
  216.   STATEMENT'LIST
  217. ┼╬─╨╥╧├ PROGRAM
  218. //
  219. ╨╥╧├ STATEMENT'LIST
  220.   // HERE WE USE ╥╬─ TO END RECURSION
  221.   ╔╞ ╥╬─<0.7 ╘╚┼╬
  222.    STATEMENT'LIST 
  223.   ┼╬─╔╞
  224.   STATEMENT
  225. ┼╬─╨╥╧├ STATEMENT'LIST
  226. //
  227. ╨╥╧├ STATEMENT
  228.   IDENTIFIER
  229.   SYMBOL(":=")
  230.   BOOLEAN
  231.   NEW'LINE
  232. ┼╬─╨╥╧├ STATEMENT
  233. //
  234. ╨╥╧├ IDENTIFIER
  235.   SYMBOL("A")
  236. ┼╬─╨╥╧├ IDENTIFIER
  237. //
  238. ╨╥╧├ BOOLEAN
  239.   ╔╞ ╥╬─<0.5 ╘╚┼╬
  240.     SYMBOL("╘╥╒┼")
  241.   ┼╠╙┼
  242.     SYMBOL("╞┴╠╙┼")
  243.   ┼╬─╔╞
  244. ┼╬─╨╥╧├ BOOLEAN
  245. //
  246. ╨╥╧├ NEW'LINE
  247.   ╨╥╔╬╘
  248. ┼╬─╨╥╧├ NEW'LINE
  249. //
  250. ╨╥╧├ SYMBOL(X$)
  251.   ╨╥╔╬╘ X$,
  252. ┼╬─╨╥╧├ SYMBOL
  253.  
  254. ╚AVE SOME PROGRAMMING FUN WITH
  255. WRITING THE WHOLE ├╧═┴╠ KERNAL IN THE
  256. SAME WAY!
  257.  
  258. ╧N THE DISK IS ALSO A PROGRAM CALLED
  259. ╚┴╔╦╒. ╔T GENERATES A TYPE OF POETRY
  260. CALLED 'HAIKU'. ╘HE HAIKU ORIGINATED
  261. IN ╩APAN ABOUT FOUR CENTURIES AGO. ╔N
  262. ITS MOST CLASSICAL VERSION THE HAIKU
  263. CONSISTS OF THREE LINES, WITH FIVE
  264. SYLLABES IN THE FIRST LINE, SEVEN
  265. SYLLABES IN THE SECOND AND FIVE IN
  266. THE THIRD.
  267.  
  268. ╘HE HAIKU-COMPOSING PROGRAM HAS A
  269. BUILT-IN VOCABULARY OF 124 WORDS. ╘HE
  270. PRODUCTION OF THE POEMS IS DECRIBED
  271. BY PRODUCTION RULES OF THE SAME KIND
  272. THAT WAS DECRIBED ABOVE. ╚OWEVER,
  273. BECAUSE THE ╩APANESE SYLLABE-SOUND IS
  274. NOT EQUIVALENT TO THE ┼NGLISH
  275. SYLLABE, POEMS WHICH ╚┴╔╦╒ CREATES
  276. ARE NOT LIMITED TO THE 5-7-5 PATTERN.
  277.  
  278. ╧NE OF THE FOUR HAIKU PATTERNS WHICH
  279. ARE USED BY THE PROGRAM, IS:
  280.  
  281. <ARTICLE><ADJECTIVE><NOUN>...
  282. <ARTICLE><NOUN><VERB>
  283.  <PREPOSITION><ARTICLE><NOUN>
  284. <ADJECTIVE><ADJECTIVE><NOUN>
  285.  
  286. GENERATING A HAIKU SUCH AS
  287.  
  288. ┴ ╙╨╥╔╬╟ ═┼┴─╧╫...
  289. ╘╚┼ ═╧╧╬ ╙╠┼┼╨╙ ╒╬─┼╥ ┴ ┬╒╙╚
  290. ┬╥╧╦┼╬ ┬╠╒┼ ╙╬╧╫╞╠┴╦┼
  291.  
  292. ╚AVE SOME FUN WITH GENERATING
  293. HAIKU'S!
  294.